BZOJ2565 最长双回文串 < Manacher >

Problem

最长双回文串

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。
输入长度为的串，求的最长双回文子串，即可将分为两部分且和都是回文串。

Input

一行由小写英文字母组成的字符串。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

1	baacaabbacabb

Sample Output

Explanation

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

HINT

对于的数据，
新加数据一组

Source

国家集训队

标签：Manacher

Solution

上稍加变化。

首先跑得到以每个位置为中心的回文串最大长度。然后考虑计算出和，分别表示以每个位置为终点和起点的最长回文串的中心点位置。如此枚举每个位置作为中间断点打擂得到最长双回文字串。

那么如何计算和呢？
对于位置，其最长回文串半径长为，那么区间中的所有位置都可以作为这个串的右端点（终点）。于是这些位置的值一定不大于，这是因为值越小，回文串越长，这样更优。所以从前往后枚举，如果中的某个点的值在前面没有确定到，那么这个点的值一定最小为。发现这样的点一定在一个区间中，所以可以记录每次更新更新到的位置，即可扫一遍得到。反着这样扫一遍即可得到。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 200000
using namespace std;
char s[MAX_M+5];
int n, f[MAX_M+5];
int L[MAX_N+5], R[MAX_N+5];
void manacher() {
    int p = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = i < r ? min(f[p*2-i], r-i) : 1;
        while (i-f[i] >= 1 && i+f[i] <= n)
            if (s[i-f[i]] == s[i+f[i]]) f[i]++;
            else break;
        if (i+f[i] > r) p = i, r = i+f[i];
    }
}
int main() {
    char str[MAX_N+5]; scanf("%s", str), n = (int)strlen(str);
    for (int i = 0; i < n; i++) s[i*2+1] = '#', s[i*2+2] = str[i];
    s[n = n*2+1] = '#', manacher(); int mx = 1, mi = n, ans = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] > 1 && i+f[i] > mx) {
            for (int j = mx; j < i+f[i]; j++) L[j] = i;
            mx = i+f[i];
        }
    for (int i = n; i >= 1; i--)
        if (f[i] > 1 && i-f[i] < mi) {
            for (int j = mi; j > i-f[i]; j--) R[j] = i;
            mi = i-f[i];
        }
    for (int i = 1; i <= n; i++) ans = max(ans, R[i]-L[i]);
    return printf("%d\n", ans), 0;
}